package com.base.dp;

public class MinDistance {
    public static void main(String[] args) {
        MinDistance minDistance = new MinDistance();
        System.out.println(minDistance.minDistance("dfkasjdlkf", "dfskd"));
    }

    public int minDistance(String word1, String word2) {


        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }

            }
        }
        return dp[m][n];

    }

    public int minDistance2(String word1, String word2) {
        return helper(word1.toCharArray(), word2.toCharArray(), 1, 1, 1);
    }

    private int helper(char[] ss1, char[] ss2, int add, int remove, int update) {
        int row = ss1.length, column = ss2.length;
        int[] dp = new int[column + 1];
        for (int i = 1; i <= column; i++) {
            dp[i] = i * add;
        }
        for (int i = 1, leftUp; i <= row; i++) {
            leftUp = (i - 1) * remove;
            dp[0] = i * remove;
            for (int j = 1, backup; j <= column; j++) {
                backup = dp[j];
                if (ss1[i - 1] == ss2[j - 1]) {
                    dp[j] = leftUp;
                } else {
                    dp[j] = Math.min(Math.min(leftUp + update, dp[j - 1] + add), dp[j] + remove);
                }
                leftUp = backup;
            }
        }
        return dp[column];
    }

}
